/*
 * @lc app=leetcode.cn id=160 lang=cpp
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
  {
    ListNode *p = headA, *q = headB;
    while (p != q)
    {
      // p=q 包含空指针的情况，也可以返回
      // if用if(p)而不是if(p->next),当面临两个/// 链表不相交时，也可以返回相交节点
      if (p)
        p = p->next;
      else
        p = headB;
      if (q)
        q = q->next;
      else
        q = headA;

      return p;
    }
  }

  // hashset方法
  //   方法二: 哈希表法
  // 使用一个hashset  遍历一个链表，hashset中存放其所有指针， 遍历另一个链表，去hashset中找相同指针
  // 时间复杂度O(m + n)    空间复杂度O(m) 或 O(n)

  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
  {
    std::unordered_set<ListNode*> set;

    ListNode* cur_a = headA;
    // 先建立A链表的hash_set
    while (cur_a)
    {
      set.insert(cur_a);
      cur_a = cur_A->next;
    }

    ListNode* cur_b = headB;
    // 再在A链表中去搜索
    while (cur_b)
    {
      if (set.find(cur_b) != set.end())  // 找到了
      {
        return cur_b;
      }
      cur_b = cur_b->next;
    }

    return nullptr;
  }
};
// @lc code=end
